Computer graphics systems are frequently used to model a scene having three-dimensional objects and display the scene on a two-dimensional display device such as a cathode ray tube or liquid crystal display. Typically, the three-dimensional objects of the scene are each represented by a multitude of polygons (or primitives) that approximate the shape of the object. Rendering the scene for display on the two-dimensional display device is a computationally intensive process. It is therefore frequently a slow process, even with today's microprocessors and graphics processing devices.
Rasterization is the process which converts the simple, geometric description of a graphics primitive into pixels for display. In order to display z-buffered, Gouraud shaded texture mapped triangles, rasterizers need to perform scan conversion, color, depth and texture interpolation, and several pixel operations, including visibility determination. To interpolate within the triangle, rasterizers need to compute slopes in the x and y directions for colors, depth and textures.
A typical primitive, as shown in FIG. 1A, is a triangle T.sub.1. Other area or surface primitives conventionally are converted into one or more triangles prior to rasterization. Consequently, the conventional rasterization process need only to handle triangles. The triangle T.sub.1 is represented by the (x,y,z) coordinates and other properties (such as colors and texture coordinates) at each of its vertices. The (x,y) coordinates of a vertex tell its location in the plane of the display. The z-coordinate tells how far the vertex is from the selected view point of the three-dimensional scene. Rasterization may be divided into three tasks: scan conversion, shading, and visibility determination.
Scan conversion utilizes the (x,y) coordinates of the vertices of each triangle to compute a set of pixels, S, which cover the triangle. Scan conversion is usually done by traveling from the left edge of the triangle to the right edge of the triangle and visiting pixels in between. Another scan conversion approach, used by Pixel Planes, is to use a processor per pixel and compute whether the pixel is inside the triangle by evaluating three edge equations, one for each edge of the triangle. In order to determine if an edge is a left edge or a right edge, the vertices of the triangle have to be sorted by their x and y coordinates. The edge that has the longest projection on the y axis is often used as the starting edge in the scan conversion process. In order to avoid visiting pixels twice along edges that are shared by triangles, a consistent rule for making ownership of such pixels mutually exclusive between adjacent triangles may be used. One such rule is that if an edge is shared by more than one triangle, the pixel is drawn if it is on the left (bottom edge, if the edge cannot be classified as left or right) edge of the triangle.
For Gouraud shading, interpolation for pixels within a triangle is done by implementing the equation below with incrementers. For example the red color component at a location (x,y) is computed as follows. EQU R(x,y)=R(x0,y0)+(x-x0)*dR/dx+(y-y0)*dR/dy
In the above, dR/dx is the slope of the red component in the x direction and dR/dy is the slope of the red component in the y direction.
There are numerous other schemes for computing colors, some of which involve more computationally intensive techniques. Common to these techniques is the interpolation of additional parameters for each pixel. In Phong shading, the normal, N, is interpolated for every pixel in the triangle. In texture mapping, S, T, and W coordinates are interpolated within the triangle in much the same way as R, G, and B are interpolated in Gouraud shading.
Visibility determination utilizes the z-coordinate, also called the depth value, of each pixel to compute the set of pixels, S.sub.v (a subset of S), which are "visible" for the triangle. The z-coordinate of each pixel may be determined by interpolation between the z-coordinate specified for each vertex of the triangle. The set S.sub.v will differ from the set S if any of the pixels in set S cover the previously rasterized triangles whose z-values are closer to the selected view point. Thus, for each triangle in the scene, a pixel is "visible" if it is in the set S.sub.v or "hidden" if it is the set S, but not in the set S.sub.v. For example, FIG. 1B shows two triangles, T1 and T2, wherein triangle T1 is partially hidden by triangle T2. Computing S.sub.v (a subset of S) includes reading the z-buffer and performing a comparison of depth values.
Typically, the position of each triangle is identified by (x,y,z) coordinates of a set of three vertices, with each vertex having a reflectance normal vector with the vertex at its origin. The reflectance normal vectors of each triangle along with information about the position of the light source:; are used to calculate the effect of the light sources on the color values determined during the shading calculations for each triangle.
Rasterization is completed by writing the colors of the set of visible pixels S.sub.v to an image buffer for display, and writing the z-coordinate of the set of visible pixels S.sub.v to a z-buffer.
Rasterization takes a considerable amount of processor cycles and hardware. As we move to create faster devices, innovative techniques to increase speed and reduce power consumption become very important.
One drawback of prior art scan conversion systems is that they do not adapt to different sizes of triangles. This leads to a performance penalty on small triangles. This shortcoming causes significant performance degradation because in several applications the average triangle has less than 20 pixels. In many cases the average triangle is even smaller.
Another drawback with prior art approaches is that they assume the worst-case triangles (with the maximum possible area) for determining the precision to which dR/dx, dR/dy, etc., need to be computed to avoid any interpolation errors for pixels in the triangle. This turns out to be a design "overkill" because worst-case triangles rarely occur. Thus existing systems use more cycles than necessary and consume more power than required.
Reading the z-buffer to determine visibility is usually a bottleneck in prior art systems because computer memories operate at much lower clock speeds than logic circuits.
Consequently, it would be desirable to have a rasterization system and method which adapts to different graphics primitive sizes, providing faster scan conversion for smaller primitives. It would also be desirable to have a rasterization system and method that adjusts the precision of calculated slopes where possible to enhance performance. Finally, it would be desirable to have a rasterization system and method that rapidly accesses the z-buffer, and the image buffer if necessary, without adversely affecting system performance.